// 杨氏矩阵：特殊的二维矩阵，每行从左往右增大，每列从上到下增大
// 查找矩阵是否含有特定元素

// 核心思路：时间复杂度 m,n分别为矩阵的两个维度。查找算法步骤如下：

// 1.从矩阵的左下角或者矩阵的右上角处开始递归运行，以左下角为例，value为要查找的值，(i,j)为当前矩阵中的位置，初始为(M-1, 0)
// 2.如果超过了矩阵范围则说明不存在这样的元素，返回false
// 3.否则的话，如果当前位置的值大于value，说明要移动位置(向上移一行)，使得数值减小，即递归使得i=i-1；如果当前位置的值小于value，说明要移动位置(向右移一列)，使得数值增大，即递归使得j=j+1；如果刚好等于value，返回当前的位置true即可

function Find(target, array) {
  // 判断是否为二维矩阵
  let m = array.length
  if (m === 0) return false
  let n = array[0].length
  let row = m - 1, col = 0
  // 左下角元素，目标元素大于当前元素，则 col++，小于当前元素，则 row--
  while (row >= 0 && col < n) {
    if (target === array[row][col]) return true
    if (target > array[row][col]) {
      col++
    } else {
      row--
    }
  }
  return false
}
module.exports = {
  Find: Find
};